package alo.p3.work;

import alo.p3.ListNode;

import java.util.ArrayDeque;
import java.util.HashMap;

//两个单向链表在某个结点相交，找到相交结点
public class FindIntersectingNode {
    //使用散列表技术
    ListNode FindIntersectingNode1(ListNode headNode1, ListNode headNode2){
        ListNode currentNode1=headNode1,currenrNode2=headNode2;
        HashMap<ListNode,Boolean> map=new HashMap<>();
        while (currentNode1!=null) {
            map.put(currentNode1,true);
            currentNode1=currentNode1.getNext();
        }
        while (currenrNode2!=null){
            if (map.containsKey(currenrNode2))
                return currenrNode2;
            else
                currenrNode2=currenrNode2.getNext();
        }
        return null;
    }
    //使用栈
    ListNode FindIntersectingNode2x(ListNode headNode1, ListNode headNode2){
        ArrayDeque<ListNode> stack1=new ArrayDeque<>();
        ListNode currentNode1=headNode1,currenrNode2=headNode2,l1=null;
        while (currentNode1!=null) {
            stack1.push(currentNode1);
            currentNode1=currentNode1.getNext();

        }
        ArrayDeque<ListNode> stack2=new ArrayDeque<>();
        while (currenrNode2!=null){
            stack2.push(currenrNode2);
            currenrNode2=currenrNode2.getNext();
        }
        //判断是否为相等--是否为空
        while (stack1.peek()==stack2.peek()&&!stack1.isEmpty()&&!stack2.isEmpty()){
            l1=stack1.pop();
            stack2.pop();
        }
        return l1;
    }




/*    //使用的是栈方法，但是没有地址的方法，只能使用hashcode重新比较
    ListNode FindIntersectingNode2(ListNode headNode1, ListNode headNode2){
        int i1=0;
        ListNode currentNode1=headNode1,currenrNode2=headNode2;
        LLStack stack1=new LLStack();
        HashMap<ListNode,Boolean> map=new HashMap<>();
        while (currentNode1!=null) {
            stack1.push(currentNode1.hashCode());
            map.put(currentNode1,true);

        }
        LLStack stack2 =new LLStack();
        while (currenrNode2!=null){
            stack2.push(currenrNode2.hashCode());
        }
        //判断是否为相等--是否为空
        while (stack1.top()==stack2.top()&&!stack1.isEmpty()&&!stack2.isEmpty()){
            i1 = stack1.pop();
            int i2 = stack2.pop();
        }
        currentNode1= BJ(headNode1, i1);
        return currentNode1;
    }

    //hashcode比较
    ListNode BJ(ListNode headNode,int i){
        ListNode currentNode=headNode;
        while (currentNode.hashCode()!=i||currentNode==null){
            if (currentNode==null)
                return null;
            else
                currentNode=currentNode.getNext();
        }
        return currentNode;
    }*/

    ListNode FindIntersectingNode3(ListNode headNode1, ListNode headNode2){
        int L1=0,L2=0,diff=0;
        ListNode c1=headNode1,c2=headNode2;
        while (c1!=null){
            L1++;
            c1=c1.getNext();
        }
        while (c2!=null){
            L2++;
            c2=c2.getNext();
        }
        if (L1<L2){
            c1=headNode2;
            c2=headNode1;
            diff=L2-L1;
        }else {
            c1=headNode1;
            c2=headNode2;
            diff=L1-L2;
        }
        for (int i=1;i<=diff;i++){
            c1=c1.getNext();
        }
        while (c1!=null&&c2!=null){
            if (c1==c2)
                return c1;
            c1=c1.getNext();
            c2=c2.getNext();
        }
        return null;
    }


}
